home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / eb_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.2 KB  |  242 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  eb_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_STRATIFIED_H
  17. #define LEDA_STRATIFIED_H
  18.  
  19. //------------------------------------------------------------------------------
  20. //  stratified tree  (van emde boas tree)
  21. // 
  22. //  Stefan Naeher (1989)
  23. //
  24. //  Modification History:
  25. //
  26. //  - Use of bounded dictionaries instead of arrays
  27. //    ( bounded dictionaries are implemented by
  28. //      dynamic perfect hashing )
  29. //
  30. //      Michael Wenzel (1990)
  31. //
  32. //
  33. //  - Dynamization
  34. //
  35. //      Michael Wenzel (1990)
  36. //
  37. //
  38. //  - Function pred
  39. //
  40. //      Michael Wenzel (1990)
  41. //
  42. //
  43. //  - Minimum and maximum not recursively stored
  44. //
  45. //      Michael Wenzel (1991)
  46. //
  47. //
  48. //  - Class l_stratified for bot-structures
  49. //      with <= 2 Elements
  50. //
  51. //      Michael Wenzel (1991)
  52. //
  53. //
  54. //  - Union b_dict for dictionary
  55. //    ( Union of bounded dictionary and array )
  56. //
  57. //      Michael Wenzel (1991)
  58. //
  59. //
  60. //------------------------------------------------------------------------------
  61.  
  62. //-----------------------------------------------------------------------------
  63. // Include & Makros
  64. //-----------------------------------------------------------------------------
  65.  
  66. #include <LEDA/impl/dp_hash.h>   
  67.  
  68.  
  69. #define pot_2(x)          ( 1 << x )
  70. #define mal_pot_2(x,y)    ( (x) << (y) )
  71. #define down(k)           ( (k) >> 1 )
  72. #define up(k)             ( down(k) + ((k) & 1) )
  73. #define high_bits(x)      ( x >> down(k) ) 
  74. #define low_bits(x)       ( x & (pot_2(down(k))-1) ) 
  75.  
  76.  
  77. //-----------------------------------------------------------------------------
  78. // definitions
  79. //-----------------------------------------------------------------------------
  80.  
  81. class l_stratified;
  82. class stratified;
  83.  
  84. typedef l_stratified* l_stratified_ptr;
  85. typedef stratified* stratified_ptr;
  86.  
  87. //-----------------------------------------------------------------------------
  88. // class definition 
  89. //-----------------------------------------------------------------------------
  90.  
  91.                                // union for dictionary
  92. class b_dict {
  93.  
  94.   union {
  95.  
  96.            GenPtr*         l;       // array
  97.            dp_hash*      d;       // bounded dictionary;
  98.  
  99.         };
  100.  
  101.  
  102. void insert(int x, GenPtr y, int k)
  103.                {
  104.                  if ( k <= 8 )  l[x] = y;        
  105.                  else           d->insert(GenPtr(x),y);  
  106.                            }
  107.  
  108. void del(int x, int k)     {
  109.                              if ( k <= 8 )  l[x] = 0; 
  110.                  else           d->del(GenPtr(x));
  111.                            }
  112.  
  113. GenPtr& lookup(int x, int k)  {
  114.                  if ( k <= 8 )  
  115.                    return l[x];
  116.                  else     
  117.                  { stp p = d->lookup(GenPtr(x));
  118.                    return d->info(p);
  119.                              }
  120.                            }
  121.  
  122.  b_dict(int);
  123. ~b_dict() {}
  124.  
  125. void clear(int);
  126.  
  127. LEDA_MEMORY(b_dict)
  128.  
  129. friend class stratified;
  130.  
  131. };
  132.  
  133. typedef b_dict* b_dict_ptr;
  134.  
  135.  
  136.                                // class for <= 2 elements
  137. class l_stratified {
  138.  
  139.  
  140. int          mi;      // minimum
  141. int          ma;      // maximum
  142.  
  143.  
  144. int size()                {
  145.                 if ( ma == -1 ) return 0 ;
  146.                 else if ( ma == mi ) return 1 ;
  147.                     else if ( ma <  mi ) return 2 ;
  148.                     else return 3;   // illegal, pointer was a stratified_ptr
  149.                   }
  150.  
  151. int insert(int x)         { if ( size() == 0 )   { mi = ma = x; return 1; }
  152.                 else if ( x < ma )   { ma = x; return 1; }
  153.                 else if ( x > mi )   { mi = x; return 1; }
  154.                 else return 0;
  155.               } 
  156.  
  157. int del(int x)            { if (size() == 1 && x == mi) { mi=ma=-1; return 1; }
  158.                 else if ( x == mi )   { mi = ma; return 1; }
  159.                 else if ( x == ma )   { ma = mi; return 1; }
  160.                 else return 0;
  161.               } 
  162.  
  163. int member(int x)         {
  164.                 return ( x == mi ) || ( x == ma );
  165.                           }
  166.  
  167. int max()                 { if ( size() <= 2 )
  168.                   return mi;
  169.                 else
  170.                   return ma;
  171.               }
  172.  
  173.  
  174. int min()                 { if ( size() <= 2 )
  175.                   return ma; 
  176.                 else
  177.                   return mi;
  178.               }
  179.  
  180. int succ(int x)           { if ( x < ma ) return ma;
  181.                 else if ( x < mi ) return mi;
  182.                 else return -1;
  183.                           }
  184.  
  185. int pred(int x)           { if ( x > mi ) return mi;
  186.                 else if ( x > ma ) return ma;
  187.                 else return -1;
  188.                           }
  189.  
  190. l_stratified(int x=-1)    { mi = ma = x; }
  191.  
  192. l_stratified(stratified*, int);
  193.  
  194.  
  195. LEDA_MEMORY(l_stratified)
  196.  
  197. friend class stratified;
  198. friend class b_dict;
  199.  
  200. };
  201.  
  202.  
  203.                                // recursive structure    
  204.  
  205. class stratified : public l_stratified { 
  206.  
  207. int            k;       // k-structure
  208. int            sz;      // size 
  209. l_stratified*  top;     // up(k)-structure
  210. b_dict_ptr     bot;     // pointer to bounded Dictionary of (k/2)-structures
  211.  
  212.  
  213. public:
  214.  
  215.  stratified(l_stratified*, int);
  216.  stratified(int);
  217. ~stratified();
  218.  
  219. int  min()        { return mi; }
  220. int  max()        { return ma; }
  221. int  size()       { return sz; }
  222.  
  223. int  min2();
  224. int  max2();
  225.  
  226. int  member(int);
  227. int  succ(int);
  228. int  pred(int);
  229.  
  230. int insert(int);
  231. int del(int);
  232.  
  233. void print();
  234.  
  235. LEDA_MEMORY(stratified)
  236.  
  237. };
  238.  
  239. typedef stratified eb_tree;
  240.  
  241. #endif
  242.